import sys
sys.setrecursionlimit(5000)


class LazyFrame(object):
    def __init__(self, frame, parent):
        self.frame = frame
        self.parent = parent
        self.evaled = {}
    def __getitem__(self, index):
        if index in self.evaled:
            return self.evaled[index]
        if index >= len(self.frame):
            return self.parent[index - len(self.frame)]
        obj = self.frame[index]
        if hasattr(obj, "eval"):
            obj = obj.eval(self.parent)
        self.evaled[index] = obj
        return obj
    def __len__(self):
        return len(self.frame)
    def __iter__(self):
        for i in range(len(self.frame)):
            return self[i]

class FunctionalElement(object):
    def run(self, *args):
        return self.eval(args)
    def accept(self, obj):
        return getattr(obj, "visit_%s" % (self.__class__.__name__,))(self)

class Call(FunctionalElement):
    def __init__(self, func, args):
        self.func = func 
        self.args = args
    def __repr__(self):
        return "Call(%r, %r)" % (self.func, self.args)
    def eval(self, frame):
        func = self.func.eval(frame)
        return func.eval(LazyFrame(self.args, frame))

class Closure(FunctionalElement):
    def __init__(self, func, args):
        self.func = func
        self.boundargs = args
    def __repr__(self):
        return "Closure(%r, %r)" % (self.func, self.boundargs)
    def eval(self, frame):
        return BoundFunc(self.func, LazyFrame(self.boundargs, frame))

class BoundFunc(FunctionalElement):
    def __init__(self, func, boundframe):
        self.func = func
        self.boundframe = boundframe
    def eval(self, frame):
        return self.func.eval(LazyFrame(frame, self.boundframe))

class Quoted(FunctionalElement):
    def __init__(self, func):
        self.func = func
    def __repr__(self):
        return "Quoted(%r)" % (self.func,)
    def eval(self, frame):
        return self.func

class Arg(FunctionalElement):
    def __init__(self, index):
        self.index = index
    def __repr__(self):
        return "Arg(%d)" % (self.index,)
    def eval(self, frame):
        return frame[self.index]

class Lazy(FunctionalElement):
    def __init__(self, globals, name):
        self.globals = globals
        self.name = name
    def eval(self, frame):
        return self.globals[self.name].eval(frame)


#===============================================================================
# primitives
#===============================================================================
primitives = {}
def functional(argcount):
    def wrapper(func):
        func.argcount = 2
        func.eval = func
        func.name = func.__name__.rstrip("_")
        func.accept = lambda obj: obj.visit_Primitive(func)
        primitives[func.name] = func
        return func
    return wrapper

@functional(2)
def add(frame):
    return frame[0] + frame[1]
@functional(2)
def sub(frame):
    return frame[0] - frame[1]
@functional(2)
def mul(frame):
    return frame[0] * frame[1]
@functional(2)
def div(frame):
    return frame[0] / frame[1]
@functional(2)
def mod(frame):
    return frame[0] % frame[1]
@functional(2)
def pow(frame):
    return frame[0] ** frame[1]
@functional(2)
def band(frame):
    return frame[0] & frame[1]
@functional(2)
def bor(frame):
    return frame[0] | frame[1]
@functional(2)
def bxor(frame):
    return frame[0] ^ frame[1]
@functional(1)
def binv(frame):
    return ~frame[0]

@functional(2)
def eq(frame):
    return frame[0] == frame[1]
@functional(2)
def ne(frame):
    return frame[0] != frame[1]
@functional(2)
def gt(frame):
    return frame[0] > frame[1]
@functional(2)
def lt(frame):
    return frame[0] < frame[1]
@functional(2)
def ge(frame):
    return frame[0] >= frame[1]
@functional(2)
def le(frame):
    return frame[0] <= frame[1]
@functional(2)
def land(frame):
    return frame[0] and frame[1]
@functional(2)
def lor(frame):
    return frame[0] or frame[1]
@functional(1)
def lnot(frame):
    return not frame[0]

@functional(2)
def append(frame):
    l = []
    l.extend(frame[0])
    l.append(frame[1])
    return l
@functional(1)
def len_(frame):
    return len(frame[0])
@functional(1)
def head(frame):
    return frame[0][0]
@functional(1)
def tail(frame):
    return frame[0][1:]
@functional(2)
def getitem_(frame):
    return frame[0][frame[1]]
@functional(3)
def getslice_(frame):
    return frame[0][frame[1]:frame[2]]
@functional(2)
def range_(frame):
    return range(frame[0], frame[1])
@functional(2)
def map(frame):
    seq = frame[0]
    func = frame[1]
    return [func.eval((item,)) for item in seq]
@functional(2)
def reduce(frame):
    seq = frame[0]
    func = frame[1]
    head = seq[0]
    tail = seq[1:]
    for v in tail:
        head = func.eval((head, v))
    return head

@functional(3)
def if_(frame):
    if frame[0]:
        return frame[1]
    else:
        return frame[2]
@functional(2)
def cond(frame):
    for i in range(len(frame) - 1):
        if frame[i][0]:
            return frame[i][1]
    return frame[len(frame) - 1]

@functional(1)
def show(frame):
    print frame[0]
    return frame[0]

#===============================================================================
# test
#===============================================================================
#addn = Call(map, Arg(0), Closure(add, Arg(1)))
#add3 = Call(addn, Arg(0), Quoted(3))
#print add3.run([3,4,5])
#
#sum = Call(reduce, Arg(0), Quoted(add))
#print sum.run([3,4,5])
















